import collections


class Solution(object):
    def longestSubstring(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """

        def search(s, k):
            c = collections.Counter(s)
            al = set()
            un = set()
            for key in c:
                if c[key] >= k:
                    al.add(key)
                else:
                    un.add(key)
            if not al:
                return 0
            if not un:
                return len(s)
            else:
                n = len(s)
                max_len = 0
                left = 0
                right = 0
                while right < n:
                    if s[right] in un:
                        if right > left:
                            max_len = max(max_len, search(s[left:right], k))
                        left = right + 1
                    right += 1
                if right > left:
                    max_len = max(max_len, search(s[left:right], k))
                return max_len

        return search(s, k)



data = Solution()
s = "bbaaacbd"
k = 3
print(data.longestSubstring(s, k))
